﻿// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace CuteAnt.Collections
{
  /// <summary>
  /// Internal helper functions for working with enumerables.
  /// </summary>
  internal static partial class EnumerableHelpers
  {
    /// <summary>
    /// Copies items from an enumerable to an array.
    /// </summary>
    /// <typeparam name="T">The element type of the enumerable.</typeparam>
    /// <param name="source">The source enumerable.</param>
    /// <param name="array">The destination array.</param>
    /// <param name="arrayIndex">The index in the array to start copying to.</param>
    /// <param name="count">The number of items in the enumerable.</param>
    internal static void Copy<T>(IEnumerable<T> source, T[] array, int arrayIndex, int count)
    {
      Debug.Assert(source != null);
      Debug.Assert(arrayIndex >= 0);
      Debug.Assert(count >= 0);
      Debug.Assert(array?.Length - arrayIndex >= count);

      if (source is ICollection<T> collection)
      {
        Debug.Assert(collection.Count == count);
        collection.CopyTo(array, arrayIndex);
        return;
      }

      IterativeCopy(source, array, arrayIndex, count);
    }

    /// <summary>
    /// Copies items from a non-collection enumerable to an array.
    /// </summary>
    /// <typeparam name="T">The element type of the enumerable.</typeparam>
    /// <param name="source">The source enumerable.</param>
    /// <param name="array">The destination array.</param>
    /// <param name="arrayIndex">The index in the array to start copying to.</param>
    /// <param name="count">The number of items in the enumerable.</param>
    internal static void IterativeCopy<T>(IEnumerable<T> source, T[] array, int arrayIndex, int count)
    {
      Debug.Assert(source != null && !(source is ICollection<T>));
      Debug.Assert(arrayIndex >= 0);
      Debug.Assert(count >= 0);
      Debug.Assert(array?.Length - arrayIndex >= count);

      int endIndex = arrayIndex + count;
      foreach (T item in source)
      {
        array[arrayIndex++] = item;
      }

      Debug.Assert(arrayIndex == endIndex);
    }

    /// <summary>Converts an enumerable to an array.</summary>
    /// <param name="source">The enumerable to convert.</param>
    /// <returns>The resulting array.</returns>
    internal static T[] ToArray<T>(IEnumerable<T> source)
    {
      Debug.Assert(source != null);

      if (source is ICollection<T> collection)
      {
        int count = collection.Count;
        if (count == 0)
        {
          return EmptyArray<T>.Instance; // Array.Empty<T>();
        }

        var result = new T[count];
        collection.CopyTo(result, arrayIndex: 0);
        return result;
      }

      var builder = new LargeArrayBuilder<T>(initialize: true);
      builder.AddRange(source);
      return builder.ToArray();
    }

    /// <summary>Converts an enumerable to an array using the same logic as List{T}.</summary>
    /// <param name="source">The enumerable to convert.</param>
    /// <param name="length">The number of items stored in the resulting array, 0-indexed.</param>
    /// <returns>
    /// The resulting array.  The length of the array may be greater than <paramref name="length"/>,
    /// which is the actual number of elements in the array.
    /// </returns>
    internal static T[] ToArray<T>(IEnumerable<T> source, out int length)
    {
      if (source is ICollection<T> ic)
      {
        int count = ic.Count;
        if (count != 0)
        {
          // Allocate an array of the desired size, then copy the elements into it. Note that this has the same
          // issue regarding concurrency as other existing collections like List<T>. If the collection size
          // concurrently changes between the array allocation and the CopyTo, we could end up either getting an
          // exception from overrunning the array (if the size went up) or we could end up not filling as many
          // items as 'count' suggests (if the size went down).  This is only an issue for concurrent collections
          // that implement ICollection<T>, which as of .NET 4.6 is just ConcurrentDictionary<TKey, TValue>.
          T[] arr = new T[count];
          ic.CopyTo(arr, 0);
          length = count;
          return arr;
        }
      }
      else
      {
        using (var en = source.GetEnumerator())
        {
          if (en.MoveNext())
          {
            const int DefaultCapacity = 4;
            T[] arr = new T[DefaultCapacity];
            arr[0] = en.Current;
            int count = 1;

            while (en.MoveNext())
            {
              if (count == arr.Length)
              {
                // MaxArrayLength is defined in Array.MaxArrayLength and in gchelpers in CoreCLR.
                // It represents the maximum number of elements that can be in an array where
                // the size of the element is greater than one byte; a separate, slightly larger constant,
                // is used when the size of the element is one.
                const int MaxArrayLength = 0x7FEFFFFF;

                // This is the same growth logic as in List<T>:
                // If the array is currently empty, we make it a default size.  Otherwise, we attempt to
                // double the size of the array.  Doubling will overflow once the size of the array reaches
                // 2^30, since doubling to 2^31 is 1 larger than Int32.MaxValue.  In that case, we instead
                // constrain the length to be MaxArrayLength (this overflow check works because of the
                // cast to uint).  Because a slightly larger constant is used when T is one byte in size, we
                // could then end up in a situation where arr.Length is MaxArrayLength or slightly larger, such
                // that we constrain newLength to be MaxArrayLength but the needed number of elements is actually
                // larger than that.  For that case, we then ensure that the newLength is large enough to hold
                // the desired capacity.  This does mean that in the very rare case where we've grown to such a
                // large size, each new element added after MaxArrayLength will end up doing a resize.
                int newLength = count << 1;
                if ((uint)newLength > MaxArrayLength)
                {
                  newLength = MaxArrayLength <= count ? count + 1 : MaxArrayLength;
                }

                Array.Resize(ref arr, newLength);
              }

              arr[count++] = en.Current;
            }

            length = count;
            return arr;
          }
        }
      }

      length = 0;
      return EmptyArray<T>.Instance; // Array.Empty<T>();
    }
  }
}
